package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * 错误写法
 * WARNNING
 * <p>
 * 要指定鸡蛋不碎的最高楼层F(0-N), 最少需要摔几个蛋.
 * <p>
 * What is the minimum number of moves that you need to know with certainty what F is,
 * regardless of the initial value of F?
 * 有点像MinMax, 最倒霉情况也要把F确定出来. 375也是minmax.
 * <p>
 * 策略问题, 动规. 有时候动规用递归写比用循环写好理解.
 * <p>
 * 如果蛋不限, 二分最快.
 * * 只有一个蛋, 从1层往上扔.
 *
 * @author tzp
 * @since 2020/9/17
 */
public class LC887 implements DynamicProblem {
    /**
     * @param K 蛋的个数
     * @param N 总楼层数 1-N
     */
    public int superEggDrop(int K, int N) {
        if (N == 0) return 0;
        if (N == 1) return 1;
        if (K == 1) return N;
        N = N + 2;
        int[][] state = new int[K + 1][N + 1];
        re(K, N, state);
        return state[K][N];
    }

    //k2 n6 n8: _ 1 2 3 4 5 6 _
    // 4 5 6
    // 4 1 2

    //k2 n7 n9: _ 1 2 3 4 5 6 7 _
    // 4 5 6
    // 4 1 2

    public int re(int k, int n, int[][] state) {
        if (n == 2) {
            state[k][n] = 1;
            return state[k][n];
        }
        if (n == 1) {
            state[k][n] = 0;
            return state[k][n];
        }
        if (k == 1) {
            state[k][n] = n - 1;
            return state[k][n];
        }
        int nextN = (int) Math.floor(n / 2.0);
        state[k][n] = re(k - 1, nextN, state) + 1;
        return state[k][n];
    }

    public static void main(String[] args) {
        System.out.println(new LC887().superEggDrop(2, 2));//2
        System.out.println(new LC887().superEggDrop(2, 3));//2
        System.out.println(new LC887().superEggDrop(2, 4));//3
        System.out.println(new LC887().superEggDrop(2, 6));//3
        System.out.println(new LC887().superEggDrop(3, 8));//4
        System.out.println(new LC887().superEggDrop(3, 14));//4
    }
}
